﻿//114. 火星词典
//已解答
//困难
//相关标签
//相关企业
//现有一种使用英语字母的外星文语言，这门语言的字母顺序与英语顺序不同。
//
//给定一个字符串列表 words ，作为这门语言的词典，words 中的字符串已经 按这门新语言的字母顺序进行了排序 。
//
//请你根据该词典还原出此语言中已知的字母顺序，并 按字母递增顺序 排列。若不存在合法字母顺序，返回  。若存在多种可能的合法字母顺序，返回其中 任意一种 顺序即可。
//
//字符串 s 字典顺序小于 字符串 t 有两种情况：
//
//在第一个不同字母处，如果 s 中的字母在这门外星语言的字母顺序中位于 t 中字母之前，那么 s 的字典顺序小于 t 。
//如果前面 min(s.length, t.length) 字母都相同，那么 s.length  t.length 时，s 的字典顺序也小于 t 。
//
//
//示例 1：
//
//输入：words = [wrt, wrf, er, ett, rftt]
//输出：wertf
//示例 2：
//
//输入：words = [z, x]
//输出：zx
//示例 3：
//
//输入：words = [z, x, z]
//输出：
//解释：不存在合法字母顺序，因此返回 。
//
//
//提示：
//
//1 = words.length = 100
//1 = words[i].length = 100
//words[i] 仅由小写英文字母组成

class Solution {
public:
    unordered_map<char, unordered_set<char>> edges; // 邻接表
    unordered_map<char, int> in; // 入度表
    bool cheak; // 边界情况

    string alienOrder(vector<string>& words) {
        // 1. 建图+ 初始化⼊度哈希表

        for (auto& s : words)
        {
            for (auto ch : s)
            {
                in[ch] = 0;
            }
        }
        int n = words.size();
        for (int i = 0; i < n; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                add(words[i], words[j]);
                if (cheak) return "";
            }
        }
        queue<char> q;
        for (auto& [a, b] : in)
        {
            if (b == 0) q.push(a);
        }
        string ret;
        while (q.size())
        {
            char t = q.front(); q.pop();
            ret += t;
            for (char ch : edges[t])
            {
                if (--in[ch] == 0) q.push(ch);
            }
        }
        for (auto& [a, b] : in)
            if (b != 0) return "";

        return ret;

    }


    void add(string& s1, string& s2)
    {
        int n = min(s1.size(), s2.size());
        int i = 0;
        for (; i < n; i++)
        {
            if (s1[i] != s2[i])
            {
                char a = s1[i], b = s2[i]; // a -> b
                if (!edges[a].count(b))
                {
                    edges[a].insert(b);
                    in[b]++;
                }
                break;
            }
        }
        if (i == s2.size() && i < s1.size()) cheak = true;
    }
};